package com.congee02;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class FindCircleNum_Topological {

    public int findCircleNum(int[][] isConnected) {

        int n =  isConnected.length;

        int[] inDegrees = new int[n];
        List<Integer>[] adjacency = new List[n];

        for (int from = 0 ; from < n ; from ++ ) {
            for (int to = 0 ; to < n ; to ++ ) {
                if (isConnected[from][to] == 0 || from == to) {
                    continue;
                }
                inDegrees[to] ++;
                if (adjacency[from] == null) {
                    adjacency[from] = new ArrayList<>();
                }
                adjacency[from].add(to);
            }
        }

        return topologicalSort(adjacency, inDegrees, n).length ;
    }

    private int[] topologicalSort(List<Integer>[] adjacency, int[] inDegrees, int num) {

        final int[] ans = new int[num];
        int k = 0;
        Queue<Integer> handle = new ArrayDeque<>();

        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) {
                handle.offer(i);
            }
        }

        while (! handle.isEmpty()) {
            int cur = handle.poll();
            ans[k ++] = cur;
            if (adjacency[cur] == null) {
                continue;
            }
            for (int neighbor : adjacency[cur]) {
                inDegrees[neighbor] --;
                if (inDegrees[neighbor] == 0) {
                    handle.offer(neighbor);
                }
            }
        }

        for (int degree : inDegrees) {
            if (degree == 0) {
                return new int[0];
            }
        }

        return ans;
    }

}
